Last week we talked about informed search strategies and remember that before we talked

about uninformed search strategies.

Important meaning that the searching agent has only the description of the problem at

his or her, its disposal.

For Romania that means you have a list, unordered list of connections possibly with costs and

you have states which you cannot look into.

Informed search strategies are essentially when we have additional information.

Then for Romania that might be the straight line distance to Bucharest or something like

this or a sense of smell or whatever you can dream up.

That's the difference.

The upshot of what we did last week was that heuristics can help dramatically.

The end result of what we were doing was A star search that given an admissible heuristic

guarantees us optimal results and if the heuristic is good, fast.

If the heuristic is bad, for instance the constant zero heuristic, we're back to uninformed

search.

If there's no information in the heuristic then we shouldn't be surprised that we're

not gaining anything.

But for many, many problems we know very good heuristics and in those things heuristics

are a game changer.

For instance straight line distance is an extremely good heuristics.

For games as we'll see we have good evaluation functions where you in chess you count your

pieces.

A pawn is one, a rook is three maybe or seven, I don't know, I don't remember those numbers.

But you can kind of look at your board and see how good it is at the moment.

Those kind of heuristics are things we have for many problem sets.

And so we looked at how does search actually work with heuristics on Thursday and the first

thing we looked at is greedy search which is kind of the simplest most thing you can

do.

Always go where your nose tells you to, directly.

Turns out that has problems.

It can get stuck in loops and even though it's very fast, it's essentially something

like depth first search, you're not always getting optimal solutions.

So greedy search uses an evaluation function which we call heuristic and that actually

is essentially an approximation or an estimation of the costs we still have to cover to the

goal.

And that's something completely different than the backwards cost function we had in

uniform cost search.

So we're looking forward.

And as opposed to uniform cost search where we actually know what the costs we've incurred

are, we can just collect them up, we don't know what the costs to the goal are, we have

to estimate them, but exactly that is the heuristic.

Here is a heuristic we looked at for informed travel in Romania which is really a heuristic.

I'm sure all of you are using when you see the map because you can gauge the straight

line distance and you would never actually, when you want to go to Bucharest, you would

never go there because the best way is in the right direction to minimize the straight

line distance.

You're using your experiences with three dimensional space to do that.

And one of the things is that if you go in the right direction, then you minimize straight

line distance.

It's even stronger.